package leetcode.other;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 */
public class A22 {
    private int n;
    private final List<String> res=new ArrayList<>();
    private char[] path;
    public List<String> generateParenthesis(int n) {
        this.n=n;
        this.path=new char[n*2];
        //要保证括号是合法的，则对于该字符串任意前缀，右括号个数<=左括号
        //所以在我们枚举第i个位置的时候，我们需要记住当前左括号个数
        //对于每个位置，在合法的前提下，可以选择填左括号，可以选择填右括号
dfs(0,0);
return res;

    }

    //i表示填了多少个括号，open表示填了多少个左括号
    public void dfs(int i, int open){
//填充完毕,返回
if(i==n*2)res.add(new String(path));

//如果当前没有达到n可以填左括号
        if(open<n){
            path[i]='(';
            dfs(i+1,open+1);
        }
        //如果当前右括号少于左括号,可以填右括号
        if(i-open<open){
            path[i]=')';//覆盖，无需回溯
            dfs(i+1,open);
        }
    }
}
